package com.fenyin.samples.study.jdk.collections.map;  

import java.util.concurrent.locks.ReentrantLock;

import com.fenyin.samples.study.util.TimeUtil;



  
public class LinkLRUCache <K,V> implements Cache<K, V>{
	
	/**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    @SuppressWarnings("rawtypes")
	transient Entry[] table;

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

//    /**
//     * The load factor for the hash table.
//     *
//     * @serial
//     */
//    final float loadFactor;

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient volatile int modCount;
    
    /**
     * The head of the doubly linked list.  被锁进行守护
     */
    private transient Entry<K,V> header;
    
    private ReentrantLock lock;
    
    final long deadTime;
    
    int capacity = 1;
    
    
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
    
    static class Entry<K,V>{
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
        Entry<K,V> before, after;
        long createTime;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
            createTime = TimeUtil.getCurrentTime17();
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
	    V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @SuppressWarnings("rawtypes")
		public final boolean equals(Object o) {
            if (!(o instanceof LinkLRUCache.Entry))
                return false;
            LinkLRUCache.Entry e = (LinkLRUCache.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        private void addBefore(Entry<K,V> existingEntry) {//在指定节点之前插入,对尾处插入
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(LinkLRUCache<K,V> lm) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }

    }
    
    public LinkLRUCache(int initialCapacity,long deadTime) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        
        // Find a power of 2 >= initialCapacity
        while (capacity < initialCapacity)
            capacity <<= 1;

        table = new Entry[capacity];
        this.lock = new ReentrantLock();
        this.deadTime = deadTime;
        init();
    }
    
    void init() {
        header = new Entry<K,V>(-1, null, null, null);
        header.before = header.after = header;
    }
    
	public V get(K key) {
        lock.lock();
        try{
        	
        	Entry<K,V> e = (Entry<K,V>)getEntry(key);
            if (e == null){
            	return null;
            }
            
        	e.recordAccess(this);
        	return e.value;
    	}finally{
    		lock.unlock();
    	}
    }
	
	@SuppressWarnings("unchecked")
	final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        Entry<K,V> indexHead = table[indexFor(hash, table.length)];
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))){
            	//如果过期了，那么就要将过期的数据进行移除
                if(System.currentTimeMillis() - e.createTime > deadTime){//时间过期
                	if(indexHead == e){
                		table[indexFor(hash, table.length)] = e.next;
                	}
            		e.remove();
            		size--;
            		return null;
                }
                return e;
            }
        }
        return null;
    }

	@SuppressWarnings({ "unchecked", "rawtypes" })
	public void put(K key, V value) {
		if (key == null){
    		return ;
    	}
    	
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
		lock.lock();
        try{
            for (Entry e = table[i]; e != null; e = e.next) {//放置的key值重复时，该逻辑进行调用
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    e.value = value;
                    e.createTime = TimeUtil.getCurrentTime17();
                    e.recordAccess(this);//如果key值重复命中，顺序模式=访问模式，那么将该节点调整到双向链表的尾部
                }
            }
            modCount++;
            addEntry(hash, key, value, i);//如果是新增的节点

    	}finally{
    		lock.unlock();
    	}
	}
	
	/**重新的方法
	 
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);//新增节点到HashTable中
        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (size>capacity) {//如果需要删除最老的映射关系时，删除双向链表的第一个元素
        	remove(eldest.key);
        }
    }
    
    /**重新的方法
    
     * This override differs from addEntry in that it doesn't resize the
     * table or remove the eldest entry.
     */
    @SuppressWarnings("unchecked")
	void createEntry(int hash, K key, V value, int bucketIndex) {
        LinkLRUCache.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);//将新增节点，添加到双向链表的尾部
        size++;
    } 


	@SuppressWarnings("unchecked")
	public void remove(K key) {
		int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
		lock.lock();
        try{
            while (e != null) {
                Entry<K,V> next = e.next;
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {//命中
                    modCount++;
                    size--;
                    if (prev == e){
                    	table[i] = next;
                    }else{
                    	prev.next = next;
                    }
                    e.remove();//将该节点重双向链表中，删除调
                }
                prev = e;
                e = next;
            }
    	}finally{
    		lock.unlock();
    	}
	}

}
